package 回溯;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 射箭比赛中的最大得分.java
 * @createTime 2023年08月09日 19:13:00
 */
public class 射箭比赛中的最大得分2212 {

	int max = 0;
	int temp = 0;
	int[] result;

	public int[] maximumBobPoints(int numArrows, int[] aliceArrows) {
		result = new int[aliceArrows.length];
		backTrace(aliceArrows, new int[result.length], 0, 0, numArrows);
		return result;
	}

	public void backTrace(int[] alice, int[] bob, int aliceIndex, int bobIndex, int numArrows) {
		//结束条件，bob 整个区间遍历完
		if (bobIndex == bob.length) {
			//这一轮的结果大于之前
			if (temp > max) {
				max = temp;
				for (int i = 0; i < bob.length; i++) {
					result[i] = bob[i];
				}
				//多余的箭
				result[bob.length - 1] += numArrows;
			}
			return;
		}
		//如果当前射箭之后能超过，则射出
		if (numArrows - alice[aliceIndex] >= 1) {
			bob[bobIndex] = alice[aliceIndex] + 1;
			temp += bobIndex;
			backTrace(alice, bob, aliceIndex + 1, bobIndex + 1, numArrows - bob[bobIndex]);
			bob[bobIndex] = 0;
			temp -= bobIndex;
		}
		//不射出
		backTrace(alice, bob, aliceIndex + 1, bobIndex + 1, numArrows - bob[bobIndex]);
	}
}
